#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
class Solution
{
public:
    int maxmiumScore(vector<int> &cards, int cnt)
    {
        int ans = 0, i = 0;
        sort(cards.rbegin(), cards.rend());
        while (i <= cnt)
        {
            ans += cards[i];
            // 偶数直接返回即为最大值
            if (ans % 2 == 0)
            {
                return ans;
            }
            else
            {
                // 奇数+偶数- cards[++cnt]
                if (cards[++cnt] + cards[cnt] % 2 != 0)
                {
                    return ans - cards[cnt] + cards[++cnt];
                }
                else
                {
                    // cards[++cnt]
                }
            }
        }
    }

    int maxmiumScore_3(vector<int> &cards, int cnt)
    {
        // 倒序
        sort(cards.begin(), cards.end(), greater<int>());
        int res = 0, lastodd = 0, lasteven = 0;
        for (int i = 0; i < cnt; i++)
        {
            res += cards[i];
            if (cards[i] % 2 == 1)
                lastodd = cards[i];
            else
                lasteven = cards[i];
        }
        if (res % 2 == 0)
            return res;

        // 前cnt 项相加为奇数
        int max1 = 0, max2 = 0;
        for (int i = cnt; i < cards.size(); i++)
        {
            // case 1 奇数-上个偶数+最近的奇数=奇数+奇数=偶数
            if (lasteven && !max1 && cards[i] % 2)
                max1 = res - lasteven + cards[i];
            // case 2 奇数-上个奇数+最近的偶数=偶数+偶数=偶数
            if (lastodd && !max2 && !(cards[i] % 2))
                max2 = res - lastodd + cards[i];
        }
        return max(max1, max2);
    }

    int maxmiumScore_4(vector<int> &cards, int cnt)
    {
        nth_element(cards.begin(), cards.begin() + cnt, cards.end(), greater<int>());
        int low[2] = {INT_MAX, INT_MAX}, sum = 0, n = cards.size();
        // low[2] are the lowest card: odd and even
        for (int i = 0; i < cnt; ++i)
        {
            int x = cards[i];
            low[x & 1] = min(low[x & 1], x);
            sum += x;
        }
        if (!(sum & 1))
        {
            return sum;
        }
        // 讨论奇数
        int ans = 0;
        for (int i = cnt; i < n; ++i)
        {
            int x = cards[i];
            //如果当前数是odd 就减lowest even 加cur
            //如果当前数是even 就减lowest odd 加cur
            //取最大
            ans = max(ans, sum - low[!(x & 1)] + x);
        }
        return ans;
    }
};

int main()
{
    Solution s;
    vector<int> cards = {1, 2, 8, 9, 4, 10, 3, 2, 6, 5, 11, 13, 13};
    int cnt = 3;
    cout << s.maxmiumScore_3(cards, cnt) << endl;
    return 0;
}